Histone deacetylase (HDAC) inhibitors that target Class I and Class II HDACs are of synthetic and therapeutic interest and ongoing clinical studies indicate that they show great promise for the treatment of cancer. Moreover, Zolinza (vorinostat) was recently approved by the FDA for the treatment of the cutaneous manifestations of cutaneous T-cell lymphoma [Nat. Rev. Drug Disc. 2007, 6, 21]. As part of a broader effort to more fully explore the structure-activity relationships (SAR) of HDAC inhibitors, we sought to identify novel HDAC inhibitor structures through iterative design by utilizing low affinity ligands as synthetic starting points for SAR development. Novel and potent HDAC inhibitors have been identified using this approach and herein we report the optimization of the recognition elements of a novel series of malonyl-derived HDAC inhibitors.